FOR · Laboratori

Verso l'esame: formulare un problema

La domanda d'esame del 2024 risolta, il progetto dei droni e una checklist di modellazione

≈ 9 min di lettura · 1988 parole

La parte di laboratorio dell’esame chiede di formulare un problema descritto a parole e di tradurlo in Python-MIP, esattamente come nei tre laboratori. Questo capitolo lavora su una domanda d’esame reale, di cui il notebook fornisce testo, insiemi, parametri e variabili ma non i vincoli, e la completa passo per passo. Segue una sintesi della descrizione del progetto (small e big project) e una checklist da usare davanti a un testo nuovo.

1. La domanda d’esame del 2024: raccolta rifiuti#

Testo

Una regione comprende dieci comuni, con le seguenti previsioni di produzione di rifiuti residenziali (in tonnellate) per l’anno prossimo:

Comune	1	2	3	4	5	6	7	8	9	10
Rifiuti (t)	1200	1300	1500	1600	1800	1900	2100	2200	2400	2500

Tre aziende offrono il servizio di raccolta, con queste caratteristiche:

Azienda	Costo di installazione	Costo di trasporto (per t)	Emissioni (t CO₂ per t)	Capacità (t per comune)
A	90000	18	0.004	800
B	110000	15	0.002	1000
C	130000	12	0.001	1200

Costi di trasporto ed emissioni sono per tonnellata raccolta. Per regolamento ambientale le emissioni totali della regione non possono superare 10 tonnellate di CO₂.

Formulare il problema di scegliere, per ogni comune, l’azienda (o le aziende) e le quantità di rifiuti raccolte da ciascuna, soddisfacendo la produzione prevista e il limite ambientale.

1.1 Insiemi, parametri, variabili#

Il notebook fornisce già i primi tre passi della scaletta.

Insiemi. $I$ i comuni, $J$ le aziende.

Parametri. $W_i$ rifiuti prodotti dal comune $i$ ; per l’azienda $j$ : $b_j$ costo di installazione, $c_j$ costo di trasporto per tonnellata, $e_j$ emissioni per tonnellata, $k_j$ capacità per comune; $M$ il tetto alle emissioni.

Variabili. $x_{ij} \in \{0, 1\}$ vale 1 se il comune $i$ usa l’azienda $j$ ; $y_{ij} \ge 0$ tonnellate raccolte dall’azienda $j$ nel comune $i$ .

Le due variabili hanno ruoli diversi e complementari, uno schema che compare in moltissimi problemi: la binaria registra una decisione «sì/no» che ha un costo fisso, la continua misura una quantità che ha un costo proporzionale. Le due vanno legate da un vincolo, altrimenti il modello potrebbe raccogliere rifiuti con un’azienda che non ha «attivato».

1.2 Vincoli e obiettivo#

Lo scheletro del notebook indica tre gruppi di vincoli, un ciclo su $i$ , un ciclo su $i$ e $j$ , e un vincolo singolo, più l’obiettivo. Li ricaviamo dal testo.

Copertura della domanda. Tutti i rifiuti di ogni comune vanno raccolti: per ogni comune $i$ , $\sum_{j \in J} y_{ij} = W_i \qquad \forall i \in I.$

Capacità e attivazione. L’azienda $j$ può raccogliere nel comune $i$ al più $k_j$ tonnellate, e solo se è stata scelta per quel comune: per ogni coppia, $y_{ij} \le k_j\, x_{ij} \qquad \forall i \in I,\ j \in J.$ È il vincolo di collegamento (linking constraint): se $x_{ij} = 0$ il termine di destra è zero e $y_{ij}$ è forzata a zero; se $x_{ij} = 1$ vale il limite di capacità. La capacità fa qui da costante «big-M» naturale, senza bisogno di inventarne una.

Emissioni. In tutta la regione, $\sum_{i \in I}\sum_{j \in J} e_j\, y_{ij} \le M.$

Obiettivo. Minimizzare il costo totale, somma dei costi di installazione delle coppie attivate e dei costi di trasporto proporzionali alle tonnellate: $\min \sum_{i \in I}\sum_{j \in J} \left( b_j\, x_{ij} + c_j\, y_{ij} \right).$

Il modello completo:

$\begin{array}{lll} \min & \displaystyle\sum_{i \in I}\sum_{j \in J} \left( b_j x_{ij} + c_j y_{ij} \right)\\ \text{s.t.} & \displaystyle\sum_{j \in J} y_{ij} = W_i & \forall i \in I\\ & y_{ij} \le k_j x_{ij} & \forall i \in I,\ j \in J\\ & \displaystyle\sum_{i \in I}\sum_{j \in J} e_j y_{ij} \le M\\ & x_{ij} \in \{0,1\},\ y_{ij} \ge 0 & \forall i \in I,\ j \in J \end{array}$

Una lettura alternativa del costo di installazione

Il testo non dice se il costo di installazione si paga una volta per azienda o una volta per ogni comune servito. Le variabili suggerite dal notebook, solo $x_{ij}$ e $y_{ij}$ , portano alla seconda lettura, adottata qui. Nella prima si aggiunge una binaria $z_j$ per azienda, si paga $\sum_j b_j z_j$ e si lega $x_{ij} \le z_j$ per ogni coppia. In sede d’esame conviene scrivere esplicitamente quale interpretazione si adotta: entrambe sono difendibili, ciò che conta è la coerenza fra variabili, vincoli e obiettivo.

Il limite di 10 tonnellate rende il problema inammissibile

Con le capacità date, il modo meno inquinante di servire un comune è usare l’azienda C fino a 1200 t, poi B fino a 1000 t, poi A. Sommando sui dieci comuni si ottengono almeno 26 t di CO₂ ( $1.2 + 1.4 + 1.8 + 2.0 + 2.4 + 2.6 + 3.0 + 3.2 + 4.0 + 4.4$ ). Con $M = 10$ non esiste alcuna soluzione ammissibile, e infatti il codice del notebook usa M = 35. È un buon promemoria: quando il solver risponde INFEASIBLE la prima cosa da controllare sono i dati, non il modello.

1.3 Il codice#

Completiamo lo scheletro del notebook. Le variabili sono dizionari indicizzati dalle coppie $(i, j)$ ; i tre gruppi di vincoli sono tre cicli; l’obiettivo è una sola xsum sulle coppie.

import mip

# Insiemi
I = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
J = [0, 1, 2]

# Parametri
W = [1200, 1300, 1500, 1600, 1800, 1900, 2100, 2200, 2400, 2500]
E = [0.004, 0.002, 0.001]
b = [90000, 110000, 130000]
k = [800, 1000, 1200]
c = [18, 15, 12]
M = 35  # tetto alle emissioni di CO2

m = mip.Model()

# Variabili
x = {(i, j): m.add_var(var_type=mip.BINARY) for i in I for j in J}
y = {(i, j): m.add_var() for i in I for j in J}

# Copertura della domanda di ogni comune
for i in I:
    m += mip.xsum(y[i, j] for j in J) == W[i]

# Capacità e attivazione, per ogni coppia comune-azienda
for i in I:
    for j in J:
        m += y[i, j] <= k[j] * x[i, j]

# Emissioni totali
m += mip.xsum(E[j] * y[i, j] for i in I for j in J) <= M

# Obiettivo: costi di installazione più costi di trasporto
m.objective = mip.minimize(mip.xsum(b[j] * x[i, j] + c[j] * y[i, j] for i in I for j in J))

m.optimize()

print("costo totale:", m.objective_value)
for i in I:
    print(f"comune {i+1}:", {'ABC'[j]: round(y[i, j].x) for j in J if y[i, j].x > 1e-6})

Con $M = 35$ il costo minimo è 2571900. La soluzione attiva 21 coppie comune-azienda: il comune 1 usa solo C (1200 t), i comuni 9 e 10 usano tutte e tre le aziende, gli altri due aziende ciascuno. Le emissioni totali sono esattamente 35 t: il vincolo ambientale è attivo, e senza di esso il modello preferirebbe più spesso l’azienda A, che costa meno da installare ma inquina di più. Vale la pena verificare a mano un comune: il 9 produce 2400 t e riceve 200 da A, 1000 da B e 1200 da C, con B e C alla capacità massima.

In parole semplici

Il modello decide due cose per ogni coppia comune-azienda: se attivare il servizio (una binaria, con costo fisso) e quanto raccogliere (una continua, con costo al chilo). Il vincolo $y \le k\,x$ impedisce di raccogliere senza attivare; la copertura impone di raccogliere tutto; il vincolo sulle emissioni costringe a preferire le aziende pulite anche quando costano di più.

2. Il progetto: rotte di droni#

Durante l’ultimo laboratorio è stato presentato lo small project, facoltativo, e la sua estensione, il big project, che può sostituire una domanda dell’esame. Quanto segue è una sintesi della descrizione data a voce; il documento ufficiale caricato sul sito del corso prevale su ogni dettaglio riportato qui.

Descrizione dello small project

Una società di consulenza usa droni per analizzare le superfici esterne degli edifici con fotocamere e sensori. Per un certo edificio è noto l’insieme dei punti in cui un drone deve fermarsi per effettuare una misura; ogni punto è identificato da tre coordinate $(x, y, z)$ , e si trascura l’orientamento del drone. La squadra dispone di quattro droni, tutti inizialmente in un punto base da cui partono contemporaneamente; ogni drone esplora un sottoinsieme di punti e torna alla base. Le velocità sono 1 m/s in salita, 2 m/s in discesa e 1.5 m/s in orizzontale; per uno spostamento con componente verticale e orizzontale il tempo è il massimo fra i due; i droni sono fermi o in moto a velocità costante, senza accelerazioni.

Si devono decidere le traiettorie dei $K$ droni in modo che ogni punto sia visitato da esattamente un drone, minimizzando il tempo in cui l’ultimo drone rientra alla base.

Due punti della griglia sono collegati se la loro distanza è al più 4 m, oppure se è al più 11 m e due delle tre coordinate differiscono di al più 0.5 m. Questa regola non vale per i collegamenti fra la base e i punti di ingresso alla griglia, definiti a parte per ciascuna delle due istanze (due edifici, ciascuno con la propria base).

Il problema va formulato come programmazione lineare intera mista e risolto con Python-MIP. L’output richiesto è, per ogni drone, la sequenza dei punti visitati (per esempio $0, 4, 11, 17, \ldots, 0$ ) e il valore dell’obiettivo. Il codice consegnato deve essere eseguibile con un unico comando su un file principale.

Alcune osservazioni utili per impostare il modello.

È una variante del TSP con più veicoli: variabili binarie sugli archi, vincoli di grado su ogni punto, e i subtour da eliminare. La differenza è che l’obiettivo non è la somma delle lunghezze ma il massimo dei tempi dei droni: si introduce una variabile $T$ da minimizzare e un vincolo «tempo del drone $k$ $\le T$ » per ogni drone. Un obiettivo di tipo minimo-massimo si linearizza sempre così.
Il tempo di ogni arco va precalcolato dai dati: $t_{ij} = \max(t^{\text{oriz}}_{ij},\ t^{\text{vert}}_{ij})$ con la velocità verticale che dipende dal verso; il grafo è quindi orientato (salire e scendere costano tempi diversi).
Il preprocessing della connettività (le regole dei 4 m e degli 11 m, e quelle speciali per la base) riduce molto il numero di archi e va fatto prima di costruire il modello, con list comprehension sulle coppie di punti.
Conviene scrivere uno script separato di verifica che legga la soluzione e controlli che sia ammissibile (ogni punto visitato una volta, ogni rotta parte e torna alla base, archi esistenti), e un disegno 3D delle rotte per un controllo visivo.
Il big project aggiunge vincoli di batteria sull’autonomia dei droni, ulteriori condizioni sui punti di ingresso e requisiti aggiuntivi per la stampa della soluzione; è pensato come estensione naturale dello small project, per confrontare il modello base con una versione più realistica.

3. Checklist per una domanda di formulazione#

Davanti a un testo nuovo, nell’ordine.

Insiemi. Elencare gli oggetti del problema e dare a ciascuno un indice. Se un oggetto ha due dimensioni (comune e azienda, nodo e nodo) ci sarà un insieme di coppie.
Parametri. Riportare ogni numero del testo in una tabella con il suo indice. Un numero «per tonnellata» moltiplica una variabile continua; un numero «fisso» moltiplica una binaria.
Variabili. Chiedersi che cosa si decide. Quantità: continue (o intere se indivisibili). Scelte sì/no: binarie. Spesso servono entrambe, collegate da $y \le k\,x$ .
Obiettivo. Una sola espressione lineare. Un «minimizzare il massimo» diventa una variabile $T$ con un vincolo per ogni termine.
Vincoli. Per ogni frase del testo che contiene «deve», «al più», «almeno», «ogni», «esattamente», un gruppo di vincoli; individuare quale indice è fissato e su quale corre la somma. I vincoli di copertura sono uguaglianze; quelli di capacità disuguaglianze; quelli di collegamento legano binarie e continue.
Natura delle variabili. Dichiararla sempre, nel modello e nel codice (var_type).
Codice. Dati come liste, variabili come liste o dizionari, un ciclo for per famiglia di vincoli, xsum per le somme, optimize(), stampa con .x. Poi controllare lo stato (OPTIMAL, INFEASIBLE) e verificare a mano almeno un vincolo sulla soluzione.
Coerenza. Ogni variabile deve comparire in almeno un vincolo e, di norma, nell’obiettivo; ogni parametro del testo deve essere usato. Un parametro inutilizzato è quasi sempre un vincolo dimenticato.

Elaborato dal notebook Exam_FOR_2024 e dalla descrizione del progetto nella registrazione della terza lezione di laboratorio. La soluzione della domanda d'esame è dell'autore, non ufficiale.